﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace ProjectEulerSolutions
{
    class CommonFunctions
    {
        /// <summary>
        /// Nalazi najveći zajednički djelitelj dva pozitivna cijela broja.
        /// </summary>
        /// <param name="a">Prvi broj</param>
        /// <param name="b">Drugi broj</param>
        /// <returns>Najveći zajednički djelitelj</returns>
        public static long GreatestCommonDivisor(long a, long b)
        {
            if (a == b)
                return a;

            if (a == 1 || b == 1)
                return 1;

            if (a <= 0 || b <= 0)
                return 0;

            if (a < b)
            {
                long temp = a;
                a = b;
                b = temp;
            }

            do
            {
                if (a % b == 0)
                    return b;
                a = a % b;
                if (b % a == 0)
                    return a;
                b = b % a;
            } while (true);
        }

        /// <summary>
        /// Daje listu znamenki nekog broja.
        /// </summary>
        /// <param name="number">Broj čije znamenke hoćemo.</param>
        /// <returns>Listu znamenki.</returns>
        public static List<int> GetDigits(int number)
        {
            List<int> result = new List<int>();
            while (number != 0)
            {
                result.Add(number % 10);
                number /= 10;
            }

            return result;
        }

        /// <summary>
        /// Daje znamenke broja, od najmanje prema najvećoj
        /// Npr: 3425 daje 5,2,4,3
        /// </summary>
        /// <param name="number">Broj čije znamenke hoćemo</param>
        /// <returns>Enumerator na znamenke</returns>
        public static IEnumerable<int> GetDigits(long number)
        {
            while (number != 0)
            {
                yield return (int)(number % 10);
                number /= 10;
            }
        }

        /// <summary>
        /// Daje znamenke broja, od najmanje prema najvećoj
        /// Npr: 3425 daje 5,2,4,3
        /// </summary>
        /// <param name="number">Broj čije znamenke hoćemo</param>
        /// <returns>Enumerator na znamenke</returns>
        public static IEnumerable<int> GetDigits(BigInteger number)
        {
            while (number != 0)
            {
                yield return (int)(number % 10);
                number /= 10;
            }
        }

        /// <summary>
        /// Daje faktorijelu nekog broja.
        /// Pošto vrlo brzo rastu, postoji velika vjerojatnost za overflow.
        /// </summary>
        /// <param name="number">Broj n čiju faktorijelu tražimo</param>
        /// <returns>n!</returns>
        public static long Factoriel(int n)
        {
            long result = 1;
            for (int i = 2; i <= n; i++)
                result *= i;

            return result;
        }

        /// <summary>
        /// Gleda jeli broj n prosti broj
        /// </summary>
        /// <param name="n">Broj za pogledat</param>
        /// <returns>True ako je prosti broj, false ako nije</returns>
        public static bool IsPrime(long n)
        {
            if (n <= 1)
                return false;

            if (n % 2 == 0 || n % 3 == 0)
                if (n == 2 || n == 3)
                    return true;
                else
                    return false;

            double limit = Math.Sqrt(n);
            if (limit == (long)limit)
                return false;

            for (long k = 6; k - 1 < limit; k += 6)
            {
                if (n % (k + 1) == 0 || n % (k - 1) == 0)
                    return false;
            }
            return true;
        }

        public static bool IsPrimeDefinite(long n)
        {
            if (n == 2)
                return true;
            if (n % 2 == 0)
                return false;

            for (long i = 3; i <= Math.Sqrt(n); i += 2)
            {
                if (n % i == 0)
                    return false;
            }
            return true;
        }

        /// <summary>
        /// Daje sve permutacije duljine k napravljene od navedenih znamenki.
        /// Broj permutacije je n!/(n-k)!, pa oprezno!
        /// Trebale bi bit poredane od manje prema većoj (odnosno, poredane su kako su ulazne znamenke poredane)
        /// Ne uključuj nulu!
        /// </summary>
        /// <param name="digits">Znamenke koje smijemo upotrebljavat (n je broj znamenki u ovoj listi)</param>
        /// <param name="k">Duljina kombinacije</param>
        /// <returns>Sve permutacije duljine k</returns>
        public static List<int> GetPermutations(List<int> digits, int k)
        {
            List<int> permutations = new List<int>();

            if (k == 0)
                return permutations;

            if (digits.Count == 1)
            {
                permutations.Add(digits[0]);
            }
            else
            {
                for (int i = 0; i < digits.Count; i++)
                {
                    var sub = GetPermutations(digits.Where((x, ind) => ind != i).ToList(), k - 1);

                    if (sub.Count == 0)
                        permutations.Add(digits[i]);

                    foreach (int comb in sub)
                    {
                        permutations.Add(comb * 10 + digits[i]);
                    }
                }
            }
            return permutations;
        }

        /// <summary>
        /// Daje sve permutacije brojeva koji sadrže odabrane znamenke
        /// Broj permutacija je n!, pa oprezno :)
        /// Trebale bi bit poredane od manje prema većoj (odnosno, poredane su kako su ulazne znamenke poredane)
        /// </summary>
        /// <param name="digits">Znamenke koje smijemo upotrebljavat (n je broj znamenki u ovoj listi)</param>
        /// <returns>Listu permutacija</returns>
        public static List<int> GetPermutations(List<int> digits)
        {
            List<int> premutations = new List<int>();

            if (digits.Count == 1)
            {
                premutations.Add(digits[0]);
            }
            else
            {
                for (int i = 0; i < digits.Count; i++)
                {
                    var sub = GetPermutations(digits.Where((x, ind) => ind != i).ToList());
                    foreach (int comb in sub)
                    {
                        int numDigits = NumberOfDigits(comb);
                        premutations.Add(comb + digits[i] * (int)Math.Pow(10, numDigits));
                    }
                }
            }

            return premutations;
        }

        /// <summary>
        /// Daje sve permutacije brojeva koji sadrže odabrane znamenke
        /// Broj permutacija je n!, pa oprezno :)
        /// Trebale bi bit poredane od manje prema većoj (odnosno, poredane su kako su ulazne znamenke poredane)
        /// </summary>
        /// <param name="digits">Znamenke koje smijemo upotrebljavat (n je broj znamenki u ovoj listi)</param>
        /// <returns>Enumeracija permutacija</returns>
        public static IEnumerable<long> GetPermutations(List<long> digits)
        {
            long result = 0;
            for (int i = 0; i < digits.Count; i++)
                result = result * 10 + digits[i];

            yield return result; //prvi

            List<int> pickingOrder = new List<int>();

            for (int i = 0; i < digits.Count; i++)
                pickingOrder.Add(0); //za početak uvijek uzimamo prvu slijedeću (indeks 0)

            while (true)
            {
                bool finished = true;
                for (int i = 1; i < pickingOrder.Count; i++)
                    if (pickingOrder[i - 1] <= pickingOrder[i])
                        finished = false; //picking order je za primjer 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

                if (finished)
                    break;

                int overflow = 1;
                int target = pickingOrder.Count;

                //gledamo gdje cemo dodat jedan
                while (overflow == 1 && target >= 0)
                {
                    target--; //prvi put je na kraj (pickingOrder.Count - 1)
                    pickingOrder[target]++; //povecamo za jedan              
                    if (pickingOrder[target] >= (pickingOrder.Count - target)) //ako je prekoracilo
                    {
                        for (int i = target; i < pickingOrder.Count; i++)
                        {
                            pickingOrder[i] = 0; //vratimo ostale na nulu
                        }
                    }
                    else
                    {
                        overflow = 0; //nije prekoracilo
                    }
                }

                List<long> tempDigitList = new List<long>(digits);
                long permutation = 0;
                for (int i = 0; i < pickingOrder.Count; i++)
                {
                    permutation *= 10;
                    permutation += tempDigitList[pickingOrder[i]];
                    tempDigitList.RemoveAt(pickingOrder[i]);
                }
                yield return permutation;
            }
        }

        /// <summary>
        /// Daje sve permutacije stringa koji sadrži naznačene znakove
        /// Broje permutacija je n!, pa oprezno! :)
        /// Trebali bi biti poredane kako su poredani ulazni znakovi
        /// </summary>
        /// <param name="characters">Znakovi koji se pojavljivaju u rezultatu</param>
        /// <returns>Enumeracija stringova s permutacijama</returns>
        public static IEnumerable<string> GetPermutation(List<char> characters)
        {
            StringBuilder sb = new StringBuilder();
            foreach (char c in characters)
                sb.Append(c);

            yield return sb.ToString();

            sb.Clear();

            List<int> pickingOrder = new List<int>();
            foreach (char c in characters)
                pickingOrder.Add(0);


            while (true)
            {
                bool finished = true;
                for (int i = 1; i < pickingOrder.Count; i++)
                    if (pickingOrder[i - 1] <= pickingOrder[i])
                        finished = false; //picking order je za primjer 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

                if (finished)
                    break;

                int overflow = 1;
                int target = pickingOrder.Count;

                //gledamo gdje cemo dodat jedan
                while (overflow == 1 && target >= 0)
                {
                    target--; //prvi put je na kraj (pickingOrder.Count - 1)
                    pickingOrder[target]++; //povecamo za jedan              
                    if (pickingOrder[target] >= (pickingOrder.Count - target)) //ako je prekoracilo
                    {
                        for (int i = target; i < pickingOrder.Count; i++)
                        {
                            pickingOrder[i] = 0; //vratimo ostale na nulu
                        }
                    }
                    else
                    {
                        overflow = 0; //nije prekoracilo
                    }
                }

                List<char> tempCharacterList = new List<char>(characters);
                sb.Clear();
                for (int i = 0; i < pickingOrder.Count; i++)
                {
                    sb.Append(tempCharacterList[pickingOrder[i]]);
                    tempCharacterList.RemoveAt(pickingOrder[i]);
                }
                yield return sb.ToString();
            }
        }

        /// <summary>
        /// Daje sve permutacije stringa koji sadrži naznačene znakove
        ///  Broj permutacije je n!/(n-k)!, pa oprezno!
        /// Trebali bi biti poredane kako su poredani ulazni znakovi
        /// </summary>
        /// <param name="characters">Znakovi koji se pojavljivaju u rezultatu</param>
        /// <param name="k">Duljina permutacije, manja ili jednaka duljini ulaznih znakova</param>
        /// <returns>Enumeracija stringova s permutacijama</returns>
        public static IEnumerable<string> GetPermutation(List<char> characters, int k)
        {
            if (k > characters.Count)
                throw new ArgumentException();

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < k; i++)
                sb.Append(characters[i]);

            yield return sb.ToString();

            sb.Clear();

            List<int> pickingOrder = new List<int>();
            for (int i = 0; i < k; i++)
                pickingOrder.Add(0);


            while (true)
            {
                bool finished = true;
                for (int i = 0; i < pickingOrder.Count; i++)
                    if (pickingOrder[i] != characters.Count - 1 - i)
                        finished = false; //picking order je za primjer 9, 8, 7, 6

                if (finished)
                    break;

                int overflow = 1;
                int target = pickingOrder.Count;

                //gledamo gdje cemo dodat jedan
                while (overflow == 1 && target >= 0)
                {
                    target--; //prvi put je na kraj (pickingOrder.Count - 1)
                    pickingOrder[target]++; //povecamo za jedan              
                    if (pickingOrder[target] >= (pickingOrder.Count - target) + (characters.Count - k)) //ako je prekoracilo
                    {
                        for (int i = target; i < pickingOrder.Count; i++)
                        {
                            pickingOrder[i] = 0; //vratimo ostale na nulu
                        }
                    }
                    else
                    {
                        overflow = 0; //nije prekoracilo
                    }
                }

                List<char> tempCharacterList = new List<char>(characters);
                sb.Clear();
                for (int i = 0; i < pickingOrder.Count; i++)
                {
                    sb.Append(tempCharacterList[pickingOrder[i]]);
                    tempCharacterList.RemoveAt(pickingOrder[i]);
                }
                yield return sb.ToString();
            }
        }

        /// <summary>
        /// Daje sve kombinacije stringa koji sadrži k (manje od n) znakova iz liste znakova
        /// Broj kombinacija je n povrh k
        /// </summary>
        /// <param name="characters">Znakovi koji se upotrebljavaju</param>
        /// <param name="k">Broj znakova u rezultatima</param>
        /// <returns>Enumeracija stringova s kombinacijama</returns>
        public static IEnumerable<string> GetCombination(List<char> characters, int k)
        {
            bool[] selection = new bool[characters.Count];

            for (int i = 0; i < selection.Length; i++)
            {
                if (i < k)
                    selection[i] = true;
                else
                    selection[i] = false;
            }

            while (true)
            {
                StringBuilder combination = new StringBuilder();
                for (int i = 0; i < selection.Length; i++)
                {
                    if (selection[i])
                        combination.Append(characters[i]);
                }
                yield return combination.ToString();

                int index = selection.Length - 1;
                if (selection[index])
                {
                    bool complete = false;
                    int count = 0;
                    while (selection[index])
                    {
                        if (index == 0)
                        {
                            complete = true;
                            break;
                        }
                        selection[index] = false;
                        count++;
                        index--;
                    }

                    if (complete)
                        break;

                    while (!selection[index])
                    {
                        if (index == 0)
                        {
                            complete = true;
                            break;
                        }
                        index--;
                    }

                    if (complete)
                        break;

                    selection[index] = false;
                    selection[index + 1] = true;
                    for (int i = 0; i < count; i++)
                    {
                        selection[index + 2 + i] = true;
                    }
                }
                else
                {
                    bool completed = false;
                    while (!selection[index])
                    {
                        if (index == 0)
                        {
                            completed = true;
                            break;
                        }
                        index--;
                    }


                    selection[index] = false;
                    selection[index + 1] = true;

                    if (completed)
                        break;
                }
            }
        }

        /// <summary>
        /// Daje sve kombinacije brojeva koji sadrži k (manje od n) znamenki iz liste znamenki
        /// Broj kombinacija je n povrh k
        /// </summary>
        /// <param name="digits">Znamenke koji se upotrebljavaju</param>
        /// <param name="k">Broj znamenki u rezultatima</param>
        /// <returns>Enumeracija brojeva s kombinacijama</returns>
        public static IEnumerable<long> GetCombination(List<int> digits, int k)
        {
            bool[] selection = new bool[digits.Count];

            for (int i = 0; i < selection.Length; i++)
            {
                if (i < k)
                    selection[i] = true;
                else
                    selection[i] = false;
            }

            while (true)
            {
                long combination = 0;
                for (int i = 0; i < selection.Length; i++)
                {
                    if (selection[i])
                    {
                        combination = combination * 10 + digits[i];
                    }
                }
                yield return combination;

                int index = selection.Length - 1;
                if (selection[index])
                {
                    bool complete = false;
                    int count = 0;
                    while (selection[index])
                    {
                        if (index == 0)
                        {
                            complete = true;
                            break;
                        }
                        selection[index] = false;
                        count++;
                        index--;
                    }

                    if (complete)
                        break;

                    while (!selection[index])
                    {
                        if (index == 0)
                        {
                            complete = true;
                            break;
                        }
                        index--;
                    }

                    if (complete)
                        break;

                    selection[index] = false;
                    selection[index + 1] = true;
                    for (int i = 0; i < count; i++)
                    {
                        selection[index + 2 + i] = true;
                    }
                }
                else
                {
                    bool completed = false;
                    while (!selection[index])
                    {
                        if (index == 0)
                        {
                            completed = true;
                            break;
                        }
                        index--;
                    }


                    selection[index] = false;
                    selection[index + 1] = true;

                    if (completed)
                        break;
                }
            }
        }


        /// <summary>
        /// Daje sve kombinacije brojeva koji sadrži k (manje od n) brojeva iz liste brojeva
        /// Broj kombinacija je n povrh k
        /// </summary>
        /// <param name="digits">Brojevi koji se upotrebljavaju</param>
        /// <param name="k">Broj brojeva u rezultatima</param>
        /// <returns>Enumeracija listi brojeva s kombinacijama</returns>
        public static IEnumerable<List<int>> GetCombinationList(List<int> numbers, int k)
        {
            bool[] selection = new bool[numbers.Count];

            for (int i = 0; i < selection.Length; i++)
            {
                if (i < k)
                    selection[i] = true;
                else
                    selection[i] = false;
            }

            while (true)
            {
                List<int> combination = new List<int>();
                for (int i = 0; i < selection.Length; i++)
                {
                    if (selection[i])
                    {
                        combination.Add(numbers[i]);
                    }
                }
                yield return combination;

                int index = selection.Length - 1;
                if (selection[index])
                {
                    bool complete = false;
                    int count = 0;
                    while (selection[index])
                    {
                        if (index == 0)
                        {
                            complete = true;
                            break;
                        }
                        selection[index] = false;
                        count++;
                        index--;
                    }

                    if (complete)
                        break;

                    while (!selection[index])
                    {
                        if (index == 0)
                        {
                            complete = true;
                            break;
                        }
                        index--;
                    }

                    if (complete)
                        break;

                    selection[index] = false;
                    selection[index + 1] = true;
                    for (int i = 0; i < count; i++)
                    {
                        selection[index + 2 + i] = true;
                    }
                }
                else
                {
                    bool completed = false;
                    while (!selection[index])
                    {
                        if (index == 0)
                        {
                            completed = true;
                            break;
                        }
                        index--;
                    }


                    selection[index] = false;
                    selection[index + 1] = true;

                    if (completed)
                        break;
                }
            }
        }

        /// <summary>
        /// Daje sve rotacije nekog broja n, uključujući i njega
        /// npr, za n=179 rezultat je 179, 791, 917
        /// </summary>
        /// <param name="n">Broj čije rotacije tražimo</param>
        /// <returns>Listu rotacija</returns>
        public static List<int> RotateNumber(int n)
        {
            List<int> result = new List<int>();
            var digits = GetDigits(n);

            for (int i = 0; i < digits.Count; i++)
            {
                int number = 0;
                for (int j = i; j < digits.Count + i; j++)
                {
                    number += digits[j % digits.Count] * (int)Math.Pow(10, j - i);
                }
                result.Add(number);
            }

            return result;
        }

        /// <summary>
        /// Daje sve rotacije nekog broja n, uključujući i njega
        /// npr, za n=179 rezultat je 179, 791, 917
        /// </summary>
        /// <param name="n">Broj čije rotacije tražimo</param>
        /// <returns>Listu rotacija</returns>
        public static IEnumerable<int> RotateNumberEnumerable(int n)
        {
            var digits = GetDigits(n);

            for (int i = 0; i < digits.Count; i++)
            {
                int number = 0;
                for (int j = i; j < digits.Count + i; j++)
                {
                    number += digits[j % digits.Count] * (int)Math.Pow(10, j - i);
                }
                yield return number;
            }
        }

        /// <summary>
        /// Daje sve palindrome, počevši od nula
        /// Palindrom je broj koji se čita isto s obje strane, npr 4471744
        /// </summary>
        /// <returns>Enumeraciju koja dava palindrome</returns>
        public static IEnumerable<int> GetPalindromes()
        {
            int i = 1;
            yield return 0;
            yield return 1;
            while (true)
            {
                i++;

                int numDigits = (int)Math.Ceiling(Math.Log10(i));

                if (i % 10 == 0)
                {
                    if ((int)Math.Pow(10, numDigits) == i)
                        numDigits++;
                }

                if (numDigits == 1)
                {
                    yield return i;
                    yield return i * 10 + i;
                }
                else
                {
                    int inverse = GetInverseNumber(i);
                    int palindrome = inverse + i * (int)Math.Pow(10, numDigits);
                    yield return palindrome;

                    palindrome = inverse % (int)Math.Pow(10, numDigits - 1) + i * (int)Math.Pow(10, numDigits - 1);
                    yield return palindrome;
                }
            }
        }

        /// <summary>
        /// Daje broj kojemu su znamenke obrnute
        /// 1435 postaje 5341
        /// </summary>
        /// <param name="n">Broj kojeg želimo obrnut</param>
        /// <returns>Obrnuti broj</returns>
        public static int GetInverseNumber(int n)
        {
            int result = 0;
            while (n > 0)
            {
                result += n % 10;
                result *= 10;
                n /= 10;
            }
            return result / 10;
        }

        /// <summary>
        /// Provjerava jeli dani string palindrom, odnosno jeli se čita isto s obje strane
        /// Npr hannah
        /// </summary>
        /// <param name="s">Potencijalni palindrom</param>
        /// <returns>True ako je palindrom, false ako nije</returns>
        public static bool IsPalindrome(string s)
        {
            for (int i = 0; i < s.Length / 2; i++)
            {
                if (s[i] != s[s.Length - 1 - i])
                    return false;
            }
            return true;
        }

        /// <summary>
        /// Provjerava jeli dani broj palindrom, odnosno jeli se čita isto s obje strane
        /// Npr 123321
        /// </summary>
        /// <param name="n">Potencijalni palindrom</param>
        /// <returns>True ako je palindrom, false ako nije</returns>
        public static bool IsPalindrome(int n)
        {
            return IsPalindrome(n.ToString());
        }

        /// <summary>
        /// Daje binarnu reprezentaciju broja n
        /// </summary>
        /// <param name="n">Broj čiju reprezentaciju tražimo</param>
        /// <returns>String koji sadrži binarni broj</returns>
        public static string GetBinaryRepresentation(int n)
        {
            string result = "";

            while (n > 0)
            {
                result = (n % 2).ToString() + result;
                n /= 2;
            }

            if (string.IsNullOrEmpty(result))
                result = "0";
            return result;
        }

        /// <summary>
        /// Gleda jeli broj sadrži svaku od danih znamenki točno jednom.
        /// </summary>
        /// <param name="n">Broj koji gledamo</param>
        /// <param name="allowedDigits">Lista znamenki.</param>
        /// <returns>True ako je pandigitalan, false ako nije</returns>
        public static bool IsPandigital(long n, List<int> allowedDigits)
        {
            if (n == 0)
                return allowedDigits.Contains(0);

            List<int> allowedCopy = new List<int>(allowedDigits);

            while (n > 0)
            {
                if (allowedCopy.Count == 0)
                    return false;

                int digit = (int)(n % 10);
                n /= 10;

                if (!allowedCopy.Contains(digit))
                    return false;

                allowedCopy.Remove(digit);
            }

            return true;
        }

        /// <summary>
        /// Daje broj znamenki pozitivnog broja n
        /// </summary>
        /// <param name="n">Pozitivni broj</param>
        /// <returns>Broj znamenki</returns>
        public static int NumberOfDigits(long n)
        {
            int numberOfDigits = (int)Math.Ceiling(Math.Log10(n));

            if ((long)Math.Pow(10, numberOfDigits) == n)
                numberOfDigits++;

            return numberOfDigits;
        }

        /// <summary>
        /// Daje broj znamenki pozitivnog broja n
        /// </summary>
        /// <param name="n">Pozitivni broj</param>
        /// <returns>Broj znamenki</returns>
        public static int NumberOfDigits(ulong n)
        {
            int numberOfDigits = (int)Math.Ceiling(Math.Log10(n));

            if ((ulong)Math.Pow(10, numberOfDigits) == n)
                numberOfDigits++;

            return numberOfDigits;
        }

        /// <summary>
        /// Daje broj znamenki pozitivnog broja n
        /// </summary>
        /// <param name="n">Pozitivni broj</param>
        /// <returns>Broj znamenki</returns>
        public static int NumberOfDigits(BigInteger n)
        {
            int numberOfDigits = (int)Math.Ceiling(BigInteger.Log10(n));

            if (BigInteger.Pow(new BigInteger(10), numberOfDigits) == n)
                numberOfDigits++;

            return numberOfDigits;
        }

        /// <summary>
        /// Daje pentagonalne brojeve
        /// </summary>
        /// <returns>Enumeraciju pentagonalnih brojeva</returns>
        public static IEnumerable<long> GetPentagonalNumbers()
        {
            long n = 0;
            while (true)
            {
                n++;
                yield return n * (3 * n - 1) / 2;
            }
        }



        /// <summary>
        /// Daje heksagonalnge brojeve
        /// </summary>
        /// <returns>Enumeraciju heksagonalnih brojeva</returns>
        public static IEnumerable<long> GetHexagonalNumbers()
        {
            long n = 0;
            while (true)
            {
                n++;
                yield return n * (2 * n - 1);
            }
        }

        /// <summary>
        /// Provjerava jeli broj triangularan
        /// </summary>
        /// <param name="n">Broj za provjerit</param>
        /// <returns>True ako je broj triangularan, false ako nije</returns>
        public static bool IsTriangularNumber(long n)
        {
            if (n < 1)
                return false;

            //formula je n(n+1) / 2
            long c = -2 * n;
            long a = 1;
            long b = 1;

            double root = Math.Sqrt(b * b - 4 * a * c);

            if ((long)root == root) // ako je cijeli broj valja
            {
                double x1 = (-b + (long)root) / (2.0 * a);
                if (x1 > 0 && (int)x1 == x1)
                    return true;

                double x2 = (-b - (long)root) / (2.0 * a);
                if (x2 > 0 && (int)x2 == x2)
                    return true;
            }
            return false;
        }

        /// <summary>
        /// Provjerva jeli broj kvardatan
        /// </summary>
        /// <param name="n">Broj za provjerit</param>
        /// <returns>True ako je n kvadratan, false ako nije</returns>
        public static bool IsSquareNumber(long n)
        {
            if (n < 1)
                return false;
            //formula je n^2
            double root = Math.Sqrt(n);
            if (root == (long)root)
                return true;
            return false;
        }

        /// <summary>
        /// Provjerava jeli broj pentagonalan
        /// </summary>
        /// <param name="n">Broj za provjerit</param>
        /// <returns>True ako je pentagonalan, false ako nije</returns>
        public static bool IsPentagonalNumber(long n)
        {
            if (n < 1)
                return false;
            //formula je c = n(3n-1)/2
            long c = -2 * n;
            long b = -1;
            long a = 3;
            //sad je 3n^2 - n - 2c = 0

            //kvardatna formula x = (-b +- sqrt(b^2 - 4ac))/2a

            double root = Math.Sqrt(b * b - 4 * a * c);

            if ((long)root == root) // ako je cijeli broj valja
            {
                double x1 = (-b + (long)root) / (2.0 * a);
                if (x1 > 0 && (int)x1 == x1)
                    return true;

                double x2 = (-b - (long)root) / (2.0 * a);
                if (x2 > 0 && (int)x2 == x2)
                    return true;
            }


            return false;
        }

        /// <summary>
        /// Provjerava jeli n hexagonalan
        /// </summary>
        /// <param name="n">Broj za provjerit</param>
        /// <returns>True ako je n hexagonalan, false ako nije</returns>
        public static bool IsHexagonalNumber(long n)
        {
            if (n < 1)
                return false;
            //formula je c = n(2n-1)
            long c = -1 * n;
            long b = -1;
            long a = 2;
            //sad je 2n^2 - n - c = 0

            //kvardatna formula x = (-b +- sqrt(b^2 - 4ac))/2a

            double root = Math.Sqrt(b * b - 4 * a * c);

            if ((long)root == root) // ako je cijeli broj valja
            {
                double x1 = (-b + (long)root) / (2.0 * a);
                if (x1 > 0 && (int)x1 == x1)
                    return true;

                double x2 = (-b - (long)root) / (2.0 * a);
                if (x2 > 0 && (int)x2 == x2)
                    return true;
            }

            return false;
        }

        /// <summary>
        /// Provjerava jeli n heptagonalan
        /// </summary>
        /// <param name="n">Broj za provjerit</param>
        /// <returns>True ako je n heptagonalan, false ako nije</returns>
        public static bool IsHeptagonalNumber(long n)
        {
            if (n < 1)
                return false;
            //formula je n(5n−3)/2
            long c = -2 * n;
            long b = -3;
            long a = 5;
            //sad je 5n^2 - 3n - 2c = 0

            //kvardatna formula x = (-b +- sqrt(b^2 - 4ac))/2a

            double root = Math.Sqrt(b * b - 4 * a * c);

            if ((long)root == root) // ako je cijeli broj valja
            {
                double x1 = (-b + (long)root) / (2.0 * a);
                if (x1 > 0 && (int)x1 == x1)
                    return true;

                double x2 = (-b - (long)root) / (2.0 * a);
                if (x2 > 0 && (int)x2 == x2)
                    return true;
            }


            return false;
        }

        /// <summary>
        /// Provjerava jeli n octagonalan
        /// </summary>
        /// <param name="n">Broj za provjerit</param>
        /// <returns>True ako je n octagonalan, false ako nije</returns>
        public static bool IsOctagonalNumber(long n)
        {
            if (n < 1)
                return false;
            //formula je c = n(3n-2)
            long c = -1 * n;
            long b = -2;
            long a = 3;
            //sad je 3n^2 - 2n - c = 0

            //kvardatna formula x = (-b +- sqrt(b^2 - 4ac))/2a

            double root = Math.Sqrt(b * b - 4 * a * c);

            if ((long)root == root) // ako je cijeli broj valja
            {
                double x1 = (-b + (long)root) / (2.0 * a);
                if (x1 > 0 && (int)x1 == x1)
                    return true;

                double x2 = (-b - (long)root) / (2.0 * a);
                if (x2 > 0 && (int)x2 == x2)
                    return true;
            }

            return false;
        }

        /// <summary>
        /// Računa binomni koeficijent, n povrh k
        /// Ne radi (zasad) ako je n manji od k
        /// Potrebno se skulirat s velikim brojevima, poradi overflowa
        /// </summary>
        /// <param name="n">N</param>
        /// <param name="k">K</param>
        /// <returns>Rezultat od n povrh k</returns>
        public static long CalculateBinome(int n, int k)
        {
            if (k == 0)
                return 1;
            long product = 1;
            for (int i = n; i > (n - k); i--)
            {
                product *= i;
            }
            return product / Factoriel(k);
        }

        public static long CalculateBinomeBig(int n, int k)
        {
            if (k == 0)
                return 1;

            if (k == 1)
                return n;

            long product = 1;

            long[] divisors = new long[k-1];
            for (int i = 2; i <= k; i++)
            {
                divisors[i - 2] = i;
            }

            bool[] usage = new bool[k - 1];
            for(int i = 0; i<usage.Length; i++)
                usage[i] = false;


            for (int i = n; i > (n - k); i--)
            {
                product *= i;
                for (int j = 0; j < divisors.Length; j++)
                {
                    if (!usage[j])
                    {
                        if (product % divisors[j] == 0)
                        {
                            product /= divisors[j];
                            usage[j] = true;
                            break;
                        }
                        else
                        {
                            long gcd = CommonFunctions.GreatestCommonDivisor(product, divisors[j]);
                            if (gcd != 1)
                            {
                                product /= gcd;
                                divisors[j] /= gcd;
                                break;
                            }
                        }
                    }
                }
            }

            while (!usage.All(x => x))
            {
                for (int j = 0; j < divisors.Length; j++)
                {
                    if (!usage[j])
                    {
                        if (product % divisors[j] == 0)
                        {
                            product /= divisors[j];
                            usage[j] = true;
                            break;
                        }
                        else
                        {
                            long gcd = CommonFunctions.GreatestCommonDivisor(product, divisors[j]);
                            if (gcd != 1)
                            {
                                product /= gcd;
                                divisors[j] /= gcd;
                                break;
                            }
                        }
                    }
                }
            }

            return product;
        }

        public static BigInteger CalculateBinomeBigInteger(int n, int k)
        {
            if (k == 0)
                return 1;

            if (k == 1)
                return n;

            BigInteger product = 1;

            BigInteger[] divisors = new BigInteger[k - 1];
            for (int i = 2; i <= k; i++)
            {
                divisors[i - 2] = i;
            }

            bool[] usage = new bool[k - 1];
            for (int i = 0; i < usage.Length; i++)
                usage[i] = false;


            for (int i = n; i > (n - k); i--)
            {
                product *= i;
                for (int j = 0; j < divisors.Length; j++)
                {
                    if (!usage[j])
                    {
                        if (product % divisors[j] == 0)
                        {
                            product /= divisors[j];
                            usage[j] = true;
                            break;
                        }
                        else
                        {
                            BigInteger gcd = BigInteger.GreatestCommonDivisor(product, divisors[j]);
                            if (gcd != 1)
                            {
                                product /= gcd;
                                divisors[j] /= gcd;
                                break;
                            }
                        }
                    }
                }
            }

            while (!usage.All(x => x))
            {
                for (int j = 0; j < divisors.Length; j++)
                {
                    if (!usage[j])
                    {
                        if (product % divisors[j] == 0)
                        {
                            product /= divisors[j];
                            usage[j] = true;
                            break;
                        }
                        else
                        {
                            BigInteger gcd = BigInteger.GreatestCommonDivisor(product, divisors[j]);
                            if (gcd != 1)
                            {
                                product /= gcd;
                                divisors[j] /= gcd;
                                break;
                            }
                        }
                    }
                }
            }

            return product;
        }

        /// <summary>
        /// Provjerava dali n ima cijeli broj kao korijen
        /// </summary>
        /// <param name="n">Broj koji provjeravamo</param>
        /// <returns>True ako ima cijeli broj kao korijen, false ako nema</returns>
        public static bool HasIntegerSquareRoot(long n)
        {
            if (n <= 0)
                throw new ArgumentException();

            long result = (long)Math.Sqrt(n);

            if (result * result == n)
                return true;

            return false;
        }

        /// <summary>
        /// Daje cjelobrojni korijen od n, ako takav postoji, inače -1
        /// </summary>
        /// <param name="n">Broj čiji korijen tražimo</param>
        /// <returns>Cjelobrojni korijen, ili -1 ako ne postoji</returns>
        public static BigInteger GetBigIntegerSquareRoot(BigInteger n)
        {
            if (n < 1)
                throw new ArgumentException();

            BigInteger lastDigit = n % 10;

            //If the last digit of a number is 0, its square ends in an even number of 0s (so at least 00) and the digits preceding the ending 0s must also form a square.
            while (lastDigit == 0)
            {
                BigInteger lastTwoDigits = n % 100;

                if (lastTwoDigits != 0)
                    return BigInteger.MinusOne;

                n /= 100;
                lastDigit = n % 10;
            }

            //A square number can end only with digits 0,1,4,6,9, or 25 in base 10
            if (lastDigit == 2 || lastDigit == 3 || lastDigit == 7 || lastDigit == 8)
                return BigInteger.MinusOne;

            //If the last digit of a number is 1 or 9, its square ends in 1 and the number formed by its preceding digits must be divisible by four.
            //If the last digit of a number is 3 or 7, its square ends in 9 and the number formed by its preceding digits must be divisible by four.
            if (lastDigit == 1 || lastDigit == 9)
            {
                if ((n / 10) % 4 != 0)
                    return BigInteger.MinusOne;
            }

            //If the last digit of a number is 2 or 8, its square ends in 4 and the preceding digit must be even.
            if (lastDigit == 4)
            {
                BigInteger lastTwoDigits = n % 100;
                if (!(lastTwoDigits == 24 || lastTwoDigits == 44 || lastTwoDigits == 64 || lastTwoDigits == 84 || lastTwoDigits == 4))
                    return BigInteger.MinusOne;
            }

            //If the last digit of a number is 5, its square ends in 25 and the preceding digits must be 0, 2, 06, or 56.
            if (lastDigit == 5)
            {
                BigInteger lastTwoDigits = n % 100;
                if (lastTwoDigits != 25)
                    return BigInteger.MinusOne;

                BigInteger lastThreeDigits = n % 1000;
                BigInteger lastFourDigits = n % 10000;

                if (!(lastThreeDigits == 25 || lastThreeDigits == 225 || lastFourDigits == 625 || lastFourDigits == 5625))
                    return BigInteger.MinusOne;
            }

            //If the last digit of a number is 4 or 6, its square ends in 6 and the preceding digit must be odd
            if (lastDigit == 6)
            {
                BigInteger lastTwoDigits = n % 100;
                if (!(lastTwoDigits == 16 || lastTwoDigits == 36 || lastTwoDigits == 56 || lastTwoDigits == 76 || lastTwoDigits == 96))
                    return BigInteger.MinusOne;
            }


            BigInteger x = 1;

            int numDigits = NumberOfDigits(n);
            if (numDigits > 1)
            {
                int power = numDigits / 2;
                x = BigInteger.Pow(10, power - 1);
            }



            while (x * x < n)
            {
                x++;
            }

            if (x * x == n)
                return x;

            return BigInteger.MinusOne;
        }

        /// <summary>
        /// Daje cjelobrojni korijen od n, ako takav postoji, inače 0
        /// </summary>
        /// <param name="n">Broj čiji korijen tražimo</param>
        /// <returns>Cjelobrojni korijen, ili 0 ako ne postoji</returns>
        public static ulong GetSquareRoot(ulong n)
        {
            if (n < 1)
                throw new ArgumentException();

            ulong lastDigit = n % 10;

            //If the last digit of a number is 0, its square ends in an even number of 0s (so at least 00) and the digits preceding the ending 0s must also form a square.
            while (lastDigit == 0)
            {
                ulong lastTwoDigits = n % 100;

                if (lastTwoDigits != 0)
                    return 0;

                n /= 100;
                lastDigit = n % 10;
            }

            //A square number can end only with digits 0,1,4,6,9, or 25 in base 10
            if (lastDigit == 2 || lastDigit == 3 || lastDigit == 7 || lastDigit == 8)
                return 0;

            //If the last digit of a number is 1 or 9, its square ends in 1 and the number formed by its preceding digits must be divisible by four.
            //If the last digit of a number is 3 or 7, its square ends in 9 and the number formed by its preceding digits must be divisible by four.
            if (lastDigit == 1 || lastDigit == 9)
            {
                if ((n / 10) % 4 != 0)
                    return 0;
            }

            //If the last digit of a number is 2 or 8, its square ends in 4 and the preceding digit must be even.
            if (lastDigit == 4)
            {
                ulong lastTwoDigits = n % 100;
                if (!(lastTwoDigits == 24 || lastTwoDigits == 44 || lastTwoDigits == 64 || lastTwoDigits == 84 || lastTwoDigits == 4))
                    return 0;
            }

            //If the last digit of a number is 5, its square ends in 25 and the preceding digits must be 0, 2, 06, or 56.
            if (lastDigit == 5)
            {
                ulong lastTwoDigits = n % 100;
                if (lastTwoDigits != 25)
                    return 0;

                ulong lastThreeDigits = n % 1000;
                ulong lastFourDigits = n % 10000;

                if (!(lastThreeDigits == 25 || lastThreeDigits == 225 || lastFourDigits == 625 || lastFourDigits == 5625))
                    return 0;
            }

            //If the last digit of a number is 4 or 6, its square ends in 6 and the preceding digit must be odd
            if (lastDigit == 6)
            {
                ulong lastTwoDigits = n % 100;
                if (!(lastTwoDigits == 16 || lastTwoDigits == 36 || lastTwoDigits == 56 || lastTwoDigits == 76 || lastTwoDigits == 96))
                    return 0;
            }


            ulong x = 1;

            int numDigits = NumberOfDigits(n);
            if (numDigits > 1)
            {
                int power = numDigits / 2;
                x = (ulong)Math.Pow(10, power - 1);
            }



            while (x * x < n)
            {
                x++;
            }

            if (x * x == n)
                return x;

            return 0;
        }

        public static bool IsPerfectSquare(long input)
        {
            double root = Math.Sqrt(input);

            long rootBits = BitConverter.DoubleToInt64Bits(root);
            long lowerBound = (long)BitConverter.Int64BitsToDouble(rootBits - 1);
            long upperBound = (long)BitConverter.Int64BitsToDouble(rootBits + 1);

            for (long candidate = lowerBound; candidate <= upperBound; candidate++)
            {
                if (candidate * candidate == input)
                {
                    return true;
                }
            }
            return false;
        }
    }
}
